{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Separate Black and White Balls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #区分黑球与白球"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>桌子上有 <code>n</code> 个球，每个球的颜色不是黑色，就是白色。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的二进制字符串 <code>s</code>，其中 <code>1</code> 和 <code>0</code> 分别代表黑色和白色的球。</p>\n",
    "\n",
    "<p>在每一步中，你可以选择两个相邻的球并交换它们。</p>\n",
    "\n",
    "<p>返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 <strong>最小步数</strong>」。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"101\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们可以按以下方式将所有黑色球移到右侧：\n",
    "- 交换 s[0] 和 s[1]，s = \"011\"。\n",
    "最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"100\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们可以按以下方式将所有黑色球移到右侧：\n",
    "- 交换 s[0] 和 s[1]，s = \"010\"。\n",
    "- 交换 s[1] 和 s[2]，s = \"001\"。\n",
    "可以证明所需的最小步数为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0111\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>所有黑色球都已经在右侧。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 不是 <code>'0'</code>，就是 <code>'1'</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [separate-black-and-white-balls](https://leetcode.cn/problems/separate-black-and-white-balls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [separate-black-and-white-balls](https://leetcode.cn/problems/separate-black-and-white-balls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"101\"', '\"100\"', '\"0111\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        a = [i for i, c in enumerate(s) if c == '0']\n",
    "        ans = 0\n",
    "        for i, j in enumerate(sorted(a)):\n",
    "            ans += abs(i-j)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        last = n-1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '1':\n",
    "                res += last - i\n",
    "                last = last - 1\n",
    "                # print(res, i, last)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n,m = 0,0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='0':\n",
    "                m+=i\n",
    "                n+=1\n",
    "        return m-(0+n-1)*n//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        res = 0\n",
    "        if \"0\" in s:\n",
    "            index = s[::-1].index(\"0\")\n",
    "        else:\n",
    "            return 0\n",
    "        n = len(s) - index\n",
    "        while i < n:\n",
    "            if s[i] == \"1\":\n",
    "                j += 1\n",
    "            if s[i] == \"0\":\n",
    "                res += j\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/11/20 19:57\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        ans = cnt = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += cnt\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        white_count = len([c for c in s if c == '0'])\n",
    "        # print(white_count)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '0':\n",
    "                if i <= white_count - 1:\n",
    "                    ret -= white_count - 1 - i\n",
    "                else:\n",
    "                    ret += i - white_count + 1\n",
    "        if white_count > 1:\n",
    "            ret += (white_count - 1) * white_count // 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        s,ans,n = [i for i in s],0,len(s)\n",
    "        l,r = 0,n\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                if l < i:\n",
    "                    l = i + 1\n",
    "                while l < r and s[l] != '0':\n",
    "                    l += 1\n",
    "                if l == r:\n",
    "                    break\n",
    "                ans += l - i\n",
    "                s[i],s[l] = s[l],s[i]\n",
    "                #print(i,l,s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        if '1' not in s or '0' not in s:\n",
    "            return 0\n",
    "        s_list = list(s)\n",
    "        left = 0\n",
    "        s_len = len(s)\n",
    "        right = s_len - 1\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            if s_list[left] == '1':\n",
    "                pass\n",
    "                while right >= left:\n",
    "                    if s_list[right] == '0':\n",
    "                        break\n",
    "                    right = right - 1\n",
    "                if right < left:\n",
    "                    break\n",
    "                res = res + (right - left)\n",
    "                s_list[left] = \"0\"\n",
    "                s_list[right] = \"1\"\n",
    "            left = left + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        t=1\n",
    "        times=0\n",
    "        n=len(s)\n",
    "        s=[int(i)for i in s]\n",
    "        n_1=sum(s)\n",
    "        n_0=n-n_1\n",
    "        i_0=0\n",
    "        i_1=n_0\n",
    "        for i in range(n):\n",
    "            # print(i,s[i],i_1,i_0)\n",
    "            if s[i]==1:\n",
    "                times+=i_1-i\n",
    "                i_1+=1\n",
    "            # else:\n",
    "            #     times+=i-i_0\n",
    "            #     i_0+=1\n",
    "        return times\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        step = i = 0;\n",
    "        j = 1;\n",
    "        l = len(s);\n",
    "        arr = []\n",
    "        for cr in s:\n",
    "           arr.append(cr) \n",
    "        \n",
    "        while(i < l and j < l):\n",
    "            b = arr[i]\n",
    "            if b == '0':\n",
    "                i = i+1\n",
    "            else:\n",
    "                if j <= i:\n",
    "                    j = i + 1\n",
    "                if j >= l:\n",
    "                    break\n",
    "                c = arr[j]\n",
    "                if c == '1':\n",
    "                    j = j + 1\n",
    "                else:\n",
    "                    step = step + j - i \n",
    "                    arr[i] = c \n",
    "                    arr[j] = b \n",
    "        return step; "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def merge_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return 0\n",
    "    mid = len(arr) // 2\n",
    "    a = arr[:mid]\n",
    "    b = arr[mid:]\n",
    "    cnt = merge_sort(a) + merge_sort(b)\n",
    "    i, n = 0, len(a)\n",
    "    for x in b:   # 根据需求修改这一段\n",
    "        while i < n and a[i] <= x:   # 左右已经有序，找到左边第一个比右边大的\n",
    "            i += 1\n",
    "        cnt += n - i\n",
    "    cur = i = j = 0\n",
    "    m = len(b)\n",
    "    while True:\n",
    "        if i == n:\n",
    "            arr[cur:] = b[j:]\n",
    "            break\n",
    "        if j == m:\n",
    "            arr[cur:] = a[i:]\n",
    "            break\n",
    "        if a[i] < b[j]:\n",
    "            arr[cur] = a[i]\n",
    "            cur += 1\n",
    "            i += 1\n",
    "        else:\n",
    "            arr[cur] = b[j]\n",
    "            cur += 1\n",
    "            j += 1\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        return merge_sort(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        path=[]\n",
    "        for i in range(n):\n",
    "            if int(s[i])==1:\n",
    "                path.append(i)\n",
    "        l=len(path)\n",
    "        for j in range(l):\n",
    "            path[l-j-1]+=j+1\n",
    "        count=0\n",
    "        for k in range(l):\n",
    "            count+=n-path[k]\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        black_idxs = []\n",
    "        for idx, cha in enumerate(list(s)):\n",
    "            if cha == '1':\n",
    "                black_idxs.append(idx)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i, idx in enumerate(black_idxs):\n",
    "            c = n - len(black_idxs) + i\n",
    "            ans += (c - idx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        ont_list = []\n",
    "        cnt = 0\n",
    "        for i,v in enumerate(s):\n",
    "            if v == '1':\n",
    "                ont_list.append(i)\n",
    "                cnt += 1\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1 , -1):\n",
    "            if cnt == 0:\n",
    "                break\n",
    "            if s[i] == '1':\n",
    "                ont_list.pop()\n",
    "                cnt -= 1\n",
    "                continue\n",
    "            idx = ont_list[-1]\n",
    "            ont_list.pop()\n",
    "            ans += i - idx\n",
    "            cnt -= 1\n",
    "            s[idx] = '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        zero_queue = collections.deque()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i]=='0':\n",
    "                zero_queue.append(i)\n",
    "            else:\n",
    "                if zero_queue:\n",
    "                    zloc = zero_queue.popleft()\n",
    "                    step = zloc-i\n",
    "                    res+=step\n",
    "                    zero_queue.append(i)\n",
    "               \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        t = []\n",
    "        for i, n in enumerate(s):\n",
    "            if n == \"0\":\n",
    "                t.append(i)\n",
    "        return sum(t) - sum(range(len(t)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        cnt = 0 if s[0] == '0' else 1\n",
    "        dp = [0] * len(s)\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                cnt += 1\n",
    "                dp[i] = dp[i - 1]\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + cnt\n",
    "        return dp[len(s)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSteps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        prefix = [0] * n\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + (s[i - 1] == '1')\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '0':\n",
    "                res += prefix[i]\n",
    "\n",
    "        return res \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
